home *** CD-ROM | disk | FTP | other *** search
/ Shareware Grab Bag / Shareware Grab Bag.iso / 007 / tbbyte.arc / QSORT.PAS < prev    next >
Encoding:
Pascal/Delphi Source File  |  1985-08-14  |  4.5 KB  |  159 lines
  1. Program Quicksort(Input,Outupt);
  2. {  An interactive quicksort program in TURBO PASCAL.  This program
  3.   is presented as an example of how to do quicksort, and is hence
  4.   interactive.  You can easily extract the main routine (function QSRT)
  5.   and the type
  6.   definition for NumberPointer and see how this program constructs
  7.   the simple linked list, so your programs can use it as a function.
  8.  
  9.   Running this program:
  10.  
  11.      Run in TURBO and it will prompt for numbers. Input numbers to sort
  12.      each followed by a newline (or return). End input of numbers with
  13.      an entry of -11111.
  14.      The program will then, almost instantaneously, spit out the list in
  15.      sorted order.
  16.  
  17.   On QUICKSORT:
  18.  
  19.   QUICKSORT was invented in the early 60's by C.A.R. (Tony) Hoare.  It is
  20.   the best sorting algorithm known (although a version called QUICKERSORT
  21.   is faster for certain cases).  The algorithm revolves around breaking a
  22.   list into sublists.  A number (say the first in the list) is chosen. Numbers
  23.   smaller than that number are placed on a list (conceptually the LEFT list),
  24.   and numbers greater than or equal are placed on another list (conceptually
  25.   the RIGHT list).  The process is then repeated, recursively, on the
  26.   sub-lists until there is only one element on each list, when they are
  27.    joined in sorted order.
  28.    Example:
  29.  
  30.    LIST:                         (3 5 1 2 4)
  31.    break on 3                     /        \
  32.    Sublists                   (1 2)       (3 5 4)
  33.    do it again:               /   \        /    \
  34.    stop when there is      (1)    (2)   (3)    (5 4)
  35.    only one element         |------|-----|\    /   \
  36.    in each list:                           \  (4)  (5)
  37.    et voila, the 'bottom'                   ---|----|
  38.    nodes of the tree are sorted.
  39.  
  40.    The number of comparisons at each level drops off very quickly. For
  41.    further explanation see Knuth, The Art Of Computer Progammingm Vol. 3
  42.    'Sorting and Searching'.
  43.  
  44.    APOLOGY
  45.    The program is uncommented.  I guess I'm just lazy...sigh...
  46.  
  47.    And Borland charges for this!?!}
  48.  
  49.  
  50. Type
  51.  
  52.    Number_ptr = ^Number_rec;
  53.    Number_rec = record
  54.                    number: Integer;
  55.                    next: Number_ptr;
  56.                 end;
  57.  
  58. Var
  59.  
  60.    First_number, New_number, Last_number: Number_ptr;
  61.    InNumber: Integer;
  62.  
  63. Procedure PrintList(List:Number_ptr);
  64.  
  65. begin
  66.    writeln;
  67.    while (List<>nil) do
  68.    begin
  69.       writeln(List^.number);
  70.       List:=List^.next;
  71.    end;
  72. end;
  73.  
  74. Function QSRT(List:Number_ptr): Number_ptr;
  75.  
  76. Var
  77.    First_hi, Last_hi, New_number, First_lo, Last_lo: Number_ptr;
  78.    Compare_number: Integer;
  79.  
  80. begin
  81.    If List=nil then
  82.       QSRT:=List
  83.    else
  84.    begin
  85.  
  86.       New(First_hi);
  87.       Last_hi:=First_hi;
  88.       New(First_lo);
  89.       Last_lo:=First_lo;
  90.       Compare_number:=List^.number;
  91.       List:=List^.next;
  92.       while List<>nil do
  93.       begin
  94.          if List^.number<Compare_number then
  95.          begin
  96.             New(New_number);
  97.             New_number^.number:=List^.number;
  98.             New_number^.next:=nil;
  99.             Last_lo^.next:=New_number;
  100.             Last_lo:=New_number;
  101.          end
  102.          else
  103.          begin
  104.             New(New_number);
  105.             New_number^.number:=List^.number;
  106.             New_number^.next:=nil;
  107.             Last_hi^.next:=New_number;
  108.             Last_hi:=New_number;
  109.          end;
  110.  
  111.       List:=List^.next;
  112.       end;
  113.       First_lo:=QSRT(First_lo^.next);
  114.       First_hi:=QSRT(First_hi^.next);
  115.  
  116.       If First_lo<>nil then
  117.       begin
  118.          Last_lo:=First_lo;
  119.          while (Last_lo^.next<>nil) do Last_lo:=Last_lo^.next;
  120.          New(New_number);
  121.          New_number^.number:=Compare_number;
  122.          New_number^.next:=First_hi;
  123.          Last_lo^.next:=New_number;
  124.       end
  125.       else
  126.       begin
  127.          New(First_lo);
  128.          First_lo^.number:=Compare_number;
  129.          First_lo^.next:=First_hi;
  130.       end;
  131.       QSRT:=First_lo;
  132.  
  133.    end;
  134. end; {QSRT}
  135.  
  136. begin
  137.  
  138.    First_number:=nil;
  139.    Write('Number?');
  140.    Read(InNumber);
  141.    while(InNumber<>-11111) do
  142.    begin
  143.       New(New_number);
  144.       New_number^.number:=InNumber;
  145.       Writeln;
  146.       If First_number = nil then
  147.          First_number:=New_number
  148.       else
  149.          Last_number^.next:=New_number;
  150.       Last_number:=New_number;
  151.       Last_number^.next:=nil;
  152.       Write('Number?');
  153.       Read(InNumber);
  154.    end;
  155.  
  156.    First_number:=QSRT(First_number);
  157.    PrintList(First_number);
  158. end.it will prompt for numbers. Input numbers to sort
  159.      each foll